package offer.offer36;

import java.util.Stack;

/**
 * @Author: wjy
 * @Date: 2021/11/2 13:42
 */
public class Solution {

    Stack<Node> nodeStack = new Stack<>();

    public static void main(String[] args) {

        Node node1 = new Node(1);
        Node node2 = new Node(3);
        Node node3 = new Node(2, node1, node2);
        Node node4 = new Node(5);
        Node node5 = new Node(4, node3, node4);

        Solution solution = new Solution();
        //solution.setNodeStack(node5);

        solution.treeToDoublyList(node5);

        int size = solution.nodeStack.size();

/*        while (true) {
            pop = solution.nodeStack.pop();
            if (pop == null) {
                break;
            }
            nodeStack

            System.out.println(pop.val);

        }*/

        for (int i = 0; i < size; i++) {
            System.out.println(solution.nodeStack.pop().val);
        }

    }

    public Node treeToDoublyList(Node root) {

        if (root == null) {
            return null;
        }

        this.setNodeStack(root);

        Node up = null, down, temp = null, head = null, tail = null;

        if (this.nodeStack.size() != 0) {
            temp = this.nodeStack.pop();
            tail = temp;
        }

        int size = this.nodeStack.size();

        for (int i = 0; i < size; i++) {
            down = this.nodeStack.pop();
            temp.left = down;
            temp.right = up;
            head = temp;
            up = temp;
            temp = down;
        }
        temp.right = up;
        head = temp;
        head.left = tail;
        tail.right = head;

        return head;
    }

    public void setNodeStack(Node node) {

        if (node == null) {
            return;
        }

        this.setNodeStack(node.left);
        nodeStack.push(node);
        this.setNodeStack(node.right);

    }

}

class Node {
    public int val;
    public Node left;
    public Node right;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val,Node _left,Node _right) {
        val = _val;
        left = _left;
        right = _right;
    }
};